package elementos_grafo;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;

import javax.swing.JFrame;
import javax.swing.JTextArea;



public class AlgoritmoDeDijkstra{
	HashMap<Vertice,Integer> d;
	HashMap<Vertice,Vertice> pi;
	JFrame jf;
	JTextArea ta;
	JTextArea ta2;

	public AlgoritmoDeDijkstra(){
		ta2 = new JTextArea();
		ta = new JTextArea();
		jf = new JFrame();
		d = new HashMap<Vertice,Integer>();
		pi = new HashMap<Vertice,Vertice>();
	}
	
	public void inicializaOrigen(Grafo G, Vertice S){
		
		for(Object objVertice : G.getVertices().getElementos()){
			Vertice vertice = (Vertice)objVertice;
			d.put(vertice, new Integer(99999));
			pi.put(vertice, null);
		}
		d.put(S, new Integer(0));
		
	}
	
	public void relax(Vertice u, Vertice v, Grafo G){
		if(d.get(v)>(d.get(u) + G.peso(u, v))){
			d.put(v,new Integer(d.get(u) + G.peso(u, v)));
			pi.put(v, u);
		}
	}
	
	public Vertice EXTRACT_MIN(Conjunto H){
		Vertice verticeMenor = (Vertice)H.getElementos().get(0);
		int menor = d.get(verticeMenor);
		
		for(int i= 1 ; i< H.getElementos().size(); i++)
			if(d.get((Vertice)H.getElementos().get(i)) < menor){
				menor = d.get(H.getElementos().get(i));
				verticeMenor = (Vertice)H.getElementos().get(i);
				}
		H.getElementos().remove(verticeMenor);

		return verticeMenor;
	}
	
	public HashMap<Vertice,Vertice> dijkstra(Grafo G, Vertice i){
		Conjunto S = new Conjunto();
		Conjunto Q = new Conjunto();
		Conjunto u;
		Vertice verticeU = new Vertice();
		inicializaOrigen(G, i);
		Q.setElementos((ArrayList<Object>)G.getVertices().getElementos().clone());
		getS(S,Q);
		HashMap<Vertice,LinkedList<Vertice>> adj = G.obtenerListaDeAdyacencia();
		LinkedList<Vertice> adyacencias = new LinkedList<Vertice>();
		while(Q.getElementos().size()!=0){
			verticeU = EXTRACT_MIN(Q);
			u= new Conjunto();
			u.getElementos().add(verticeU);
			S = S.union(u);
			adyacencias = adj.get(verticeU);
			for(Vertice v : adyacencias)
				relax(verticeU,v,G);
			getS(S,Q);

		}
		return pi;
	}
	
	
	public void getS(Conjunto S, Conjunto Q){
		String conjuntoS="";
		String conjuntoQ="";
		String distancias = "";
		String predecesores = "";
		jf.setBounds(430, 400, 530, 250);
		jf.setResizable(true);
		jf.setVisible(true);
		jf.getContentPane().setLayout(null);
		jf.getContentPane().add(ta);
		jf.getContentPane().add(ta2);
		jf.setResizable(false);
		ta.setBounds(10, 10, 200, 200);
		ta2.setBounds(210, 10, 300, 200);
		for(Object objVertice : S.getElementos()){
			Vertice v = (Vertice)objVertice;
			conjuntoS += v.getNombre()+",  ";
		}
		for(Object objVertice : Q.getElementos()){
			Vertice v = (Vertice)objVertice;
			conjuntoQ += v.getNombre()+",  ";
		}
		Iterator<Map.Entry<Vertice,Integer>> it = d.entrySet().iterator();
		while (it.hasNext()) {
		Map.Entry<Vertice,Integer> e = (Map.Entry<Vertice,Integer>)it.next();
		distancias += e.getValue()+",   ";
		}

		Iterator<Map.Entry<Vertice,Vertice>> it2 = pi.entrySet().iterator();
		while (it2.hasNext()) {
		Map.Entry<Vertice,Vertice> e = (Map.Entry<Vertice,Vertice>)it2.next();
		if(e.getValue() != null)
			predecesores +=  e.getValue().getNombre()+",   ";
		else
			predecesores +=  "null,  ";
		}		
		ta.append("S = {"+conjuntoS+"}\n"+"Q = {"+conjuntoQ+"}\n");
		ta2.append("d = {" + distancias +"}\n"+"pi = {"+predecesores+"}\n");
	}
	
}
